Pixel classification is sometimes referred to as segmentation, in which various segments of an image are identified as belonging to individual product component types. Pixel classification is commonly used in quality control or product inspection applications, particularly in the food products industry, in order to distinguish between acceptable and defective product.
Food products are often graded by their appearance. Green beans, for instance, are expected to be a uniform shade of green. Defects within a single green bean might be formed by white, brown, black, or other discolored areas. It is desirable to detect green beans having such defective areas, and to separate them from green beans without such defects. It may also be desirable to quantify the defective areas, and to reject as defective only those green beans having more than a specified area of any certain type of defect.
Before automated product inspection can take place, an image of the product must be captured in a form which is meaningful to a computer or data processor; a form in which the image is represented by a series or array of numbers. Electronic video systems do this by dividing an image into a number of discrete picture elements or "pixels." Each pixel has an associated color value, representing the hue and intensity of that portion of the image which corresponds to the pixel.
In a monochrome or black-and-white video system, the color value is specified by a single variable which ranges from 0 to n. The color value in such a case represents the absolute light intensity of the image area corresponding to the pixel. A color value of 0 corresponds to black, and a color value of n corresponds to white. Intermediate color or intensity values correspond to progressing levels of grey.
In a color video system it is necessary to record intensities for at least two different ranges of colors. Three different color ranges, designated red, green, and blue are typically used. Thus, a single color value in a color video system might be specified by three or more discrete variables or intensity values, r, g, and b, corresponding to intensities of red, green, and blue.
In segmenting a video image, it is necessary to classify each possible color value as one of a plurality of component types. A component type is defined as an area of the product representing a single quality classification such as "acceptable" product, "white defect" product, "brown defect" product, or another classification, depending on the nature of the product. In practice, it is desirable to define a number of such quality classifications corresponding not only to visually identifiable product areas, but also to areas representing foreign objects such as rocks or wood. Segmenting the video image is often the first and most critical step in a detailed image analysis which includes many subsequent analytical steps.
In a monochrome system, in which each pixel is represented by a color value having only one intensity value, it is common to set one or more thresholds for purposes of color value or pixel classification. The relationship of each pixel's color value to the thresholds determines that pixel's classification. Because the color value is single-dimensioned, e.g., a function of a single variable, the operator is able to easily conceptualize the thresholds and vary them to obtain the desired segmentation results. Varying the single-dimensioned thresholds is a simple matter of increasing or decreasing their values.
Pixel classification becomes somewhat more difficult when the color value has two or three variables or dimensions, such as in a color video system having r, g, and b intensity values. Simple thresholds, if used, would need to be set for each of the three dimensions. Not only would such thresholds be difficult for an operator to conceptualize, but the number of variables would make meaningful and proper adjustment nearly impossible. In addition, simple thresholds allow specification of only a rectangularly shaped space in the three-dimensional space defined by the possible color values, while actual component areas usually contain color values forming irregular shapes within the three-dimensional color value space. Therefore, color analysis systems generally require more sophisticated methods of pixel or color value classification than are used with black-and-white systems.
One approach to color image classification, used in a diamond inspection apparatus, is described in U.S. Pat. No. 4,951,825 to Hawkins et al., entitled "Apparatus for Classifying Particulate Material." The Hawkins patent describes a "learning" process in which one class at a time of pre-sorted diamonds are introduced into the machine. The machine stores the color values obtained during the learning process and subsequently compares color values in sample diamonds with the stored values to determine the closest match.
The method described by Hawkins et al. might be suitable when it is not necessary to detect specific features occurring within a single image. The method is not sufficient, however, when component types contained within the same image must be differentiated from each other, or when it is required to detect the presence of small component types within larger articles.
A more suitable approach for classifying a number of component types, all contained within the same image, is described in U.S. Pat. No. 4,807,163 to Gibbons, entitled "Method and Apparatus for Digital Analysis of Multiple Component Visible Fields." Gibbons describes segmenting an image of a human scalp to quantify hair loss.
In the Gibbons method, subareas of a visual image, each containing only a single component type (bald or not bald), are initially identified or .selected by an operator from a sample image. A histogram is then compiled for each identified sub-area, and mean intensity values are determined for each component type based on the histogram. The intensity value for each pixel is then compared to the mean intensity values. If the pixel intensity value falls within a predetermined range of any component mean intensity value, it is classified as that component type. The pixels are then counted to determine the number of pixels classified as bald.
In an alternative embodiment, Gibbons compares the mean intensity value for two component types to determine an average intensity value. This average intensity value is then used as a threshold, with higher values being classified as one component type and lower values being classified as the other component type.
Gibbons does not address the problem of setting thresholds in the three-dimensional space of a color analysis system. In fact, the prior art has to this date failed to adequately address the problem of accurately setting classification parameters in a color system. Most prior art systems are directed to single color systems or are limited to distinguishing between two component types. Many of these systems also require operator intervention prior to analyzing each image.
The prior art classification methods are not easily adaptable to color systems in which pixels are represented by more than one variable or intensity value. For instance, it is not clear in the Gibbons disclosure how intensity value comparisons could be made in each dimension of a three-color system. Even if the Gibbons methods were adaptable to color systems, the simple thresholds described would make it impossible to set accurate boundaries for component types occupying irregular three-dimensional spaces.
In addition, the prior art, including the Gibbons patent, does not adequately account for cases in which the component types have overlapping histograms--when a specific color value occurs in more than one component type. In such cases, it is necessary to determine the proper component type classification for each color value. The Gibbons analysis arbitrarily selects a threshold based on mean histogram values. This threshold has no correlation to the desired classification priority.
The invention described below provides means and methods for classifying pixels and their color values as one of many component types, taking into account relative classification priorities and other factors, and resulting in more reliable classification. In addition, the methods described below adapt themselves automatically to changing product loads and conditions.